// @algorithm @lc id=600 lang=cpp 
// @title non-negative-integers-without-consecutive-ones


// @test(5)=5
// @test(1)=2
// @test(2)=3
// @test(3)=3
class Solution {
public:
    int findIntegers(int n) {
        int N = 30, i = 2; 
        vector<int> dp(N+1, 1);
        for(; i<N+1; i++)
            dp[i] = dp[i-1] + dp[i-2];
        
        int ans = 0, II = 0;
        for(i = N; i>0; i--){
            int b = n & (1<<(i-1));
            if(b){
                ans += dp[i];
                if(II) break;
                n -= b;
            }
            II = b;
        }
        return ans + (i==0);
    }
};